#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
        // const int INF = 0x3f3f3f3f;
        // int numSquares(int n) {
        //     vector<int> nums;
        //     for (int i = 1; i * i <= n; ++i) {
        //         nums.push_back(i * i);
        //     }
        //     int sz = nums.size();
        //     vector<vector<int>> dp(sz+1, vector<int>(n+1, INF));
        //     for (int i = 0; i <= sz; ++i) {
        //         dp[i][0] = 0;
        //     }
        //     for(int i = 1; i <= sz; i++)
        //     {
        //         for(int j = 0; j <= n; j++)
        //         {
        //             dp[i][j] = dp[i-1][j];
        //             if(j>=nums[i-1]) dp[i][j] = min(dp[i][j], dp[i][j-nums[i-1]]+1);
        //         }
        //     }
        //     return dp[sz][n];
        // }
    
        const int INF = 0x3f3f3f3f;
        int numSquares(int n) {
            vector<int> nums;
            for (int i = 1; i * i <= n; ++i) {
                nums.push_back(i * i);
            }
            vector<int> dp(n+1, INF);
            dp[0] = 0;
            for(auto num : nums)
            {
                for(int j = num; j <= n; j++)
                {
                    dp[j] = min(dp[j], dp[j-num]+1);
                }
            }
            return dp[n];
        }
    };